#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>

using std::vector;
using std::string;
using std::unordered_map;

namespace wang {
    static unordered_map<char, vector<char>> map{
        {'2',{'a','b','c'}},
        {'3',{'d','e','f'}},
        {'4',{'g','h','i'}},
        {'5',{'j','k','l'}},
        {'6',{'m','n','o'}},
        {'7',{'p','q','r','s'}},
        {'8',{'t','u','v'}},
        {'9',{'w','x','y','z'}}
    };
}

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ret;
        string now = "";
        combine(ret, digits, now, 0);
        return ret;
    }

    static void combine(vector<string>& v, string& digits, string& now, int index) {
        for (char c : wang::map[digits[index]]) {
            now += c;
            if (index < digits.size() - 1) {
                combine(v, digits, now, index + 1);
            }
            else {
                v.push_back(now);
            }
            now.erase(now.end() - 1);
        }
    }
};